package datastructure.link;

import java.util.ArrayList;
import java.util.List;

public class LC19 {
    /**
     * @param head
     * @param n
     * @return 使用两次扫描的方法，第一次统计出链表数量
     * 第二次根据链表数量计算出需要删除的元素下表，然后进行删除
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int count = 0;
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode current = pre;
        while (current.next != null) {
            count++;
            current = current.next;
        }
        int index = count - n;
        current = pre;
        int i = 0;
        while (current.next != null) {
            if (i == index) {
                current.next = current.next.next;
                return pre.next;
            }
            i++;
            current = current.next;
        }
        return pre.next;
    }

    //利用额外空间进行存储，只需要一次遍历，但是使用了额外空间，而且可能会涉及到集合的扩容复杂度
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode current = pre;
        List<ListNode> list = new ArrayList<>();
        while (current != null) {
            list.add(current);
            current = current.next;
        }
        int size = list.size();
        int index = size - n;
        list.get(index - 1).next = index + 1 == size ? null : list.get(index + 1);
        return list.get(0).next;
    }

    //快慢指针，针对倒数第几个的场景, 先让快指针走n+1个长度，因为方便后面慢指针直接指向下下个节点
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode slow = pre;
        ListNode fast = pre;
        //快指针先走n+1个长度
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        //遍历到fast为null， 此时slow指针指向的是倒数第n+1个元素，此时就可以直接改变next指针达到删除的作用， 这就是为什么fast要走n+1个长度的原因
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        //如果慢指针的next是null说明遍历到了最后一个元素了，还是没找到需要删除的下表，此时就不进行删除
        if (slow.next != null) {
            slow.next = slow.next.next;
        }
        return pre.next;
    }
}
